# coding: utf-8

import sys
import operator
import ast
sys.path.append('../3_data_structure')
from BinaryTree import BinaryTree
from stack import Stack



def build_parse_tree(expression):
    tokens = expression.split()

    tree = BinaryTree('')
    stack = Stack()
    stack.push(tree)

    current_tree = tree
    for token in tokens:
        if token == '(':
            current_tree.insert_left('')
            stack.push(current_tree)
            current_tree = current_tree.get_left_child()

        elif token in ['+', '-', '*', '/']:
            current_tree.set_root_val(token)
            current_tree.insert_right('')
            stack.push(current_tree)
            current_tree = current_tree.get_right_child()

        elif token == ')':
            current_tree = stack.pop()

        else:
            try:
                current_tree.set_root_val(int(token))
                current_tree = stack.pop()
            except ValueError:
                raise ValueError("token '{}' is not a valid integer".format(token))
    return tree


def evaluate(parse_tree):
    opers = {
        '+': operator.add,
        '-': operator.sub,
        '*': operator.mul,
        '/': operator.truediv
    }

    left = parse_tree.get_left_child()
    right = parse_tree.get_right_child()

    if left and right:
        fn = opers[parse_tree.get_root_val()]
        return fn(evaluate(left), evaluate(right))
    else:
        return parse_tree.get_root_val()


expression = '( ( 3 + 5 ) * 3 )'
print(evaluate(build_parse_tree(expression)))
ast.dump(ast.parse(expression))
